#include "stack_queue.h"
#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>
using namespace std;

listNode::listNode(){
    data = 0, next = NULL;
}

listNode::listNode(int nodeData, listNode* succ){
    data = nodeData, next = succ;
}
//初始化栈
MyStack::MyStack(){
    topNode = NULL,stackSize = 0;
}
//销毁栈
MyStack::~MyStack() {
    while (topNode != nullptr) {
        listNode* tempNode = topNode;
        topNode = topNode->next;
        delete tempNode;  // 释放当前节点
    }
    stackSize = 0;  // 清空栈的大小计数
}
//入栈
bool MyStack::push(const int& item){
    listNode* newNode = new listNode(item, topNode);
    if (newNode == nullptr) {
        return false;  // 内存分配失败
    }
    topNode = newNode;
    stackSize++;
    return true;
}
//出栈
bool MyStack::pop(int& item){
    if (topNode == nullptr) {
        return false;  // 栈为空
    }
    listNode* tempNode = topNode;
    item = topNode->data;
    topNode = topNode->next;
    delete tempNode;
    stackSize--;
    return true;
}
//取出栈顶元素
bool MyStack::getTop(int& item) {
    if (topNode == nullptr) {
        return false;  // 栈为空
    }
    item = topNode->data;
    return true;
}
//输出栈内元素
void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}
//初始化队列
MyQueue::MyQueue(const int& cap){
    capacity = cap,front = 0, rear = 0;
    queue = new int[capacity];
}
//销毁队列
MyQueue::~MyQueue() {
    delete[] queue;
}
// 入队操作
bool MyQueue::enQueue(const int& item) {
    if ((rear + 1) % capacity == front) {
        return false; // 队列已满
    }
    queue[rear] = item; // 添加元素
    rear = (rear + 1) % capacity; // 更新队尾索引
    return true;
}
// 出队操作
bool MyQueue::deQueue(int& item) {
    if (front == rear) {
        return false; // 队列为空
    }
    item = queue[front]; // 获取队头元素
    front = (front + 1) % capacity; // 更新队头索引
    return true;
}
// 获取队首元素
bool MyQueue::getFront(int& item) {
    if (front == rear) {
        return false; // 队列为空
    }
    item = queue[front]; // 返回队头元素
    return true;
}
//输出队列元素
void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}
// 检查队列是否满
bool MyQueue::isFull() {
    return (rear + 1) % capacity == front; // 判断队列是否满
}
bool postfixExpression(const string& infix, string& result) {
    MyStack operatorStack;
    stringstream postfix;
    char token;
    unordered_map<char, int> precedence = {
        {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}
    };
    for (size_t i = 0; i < infix.size(); ++i) {
        token = infix[i];

        if (isdigit(token)) {
            // 如果是数字，直接添加到输出
            postfix << token ;//<< ' ';
        } else if (token == '(') {
            // 遇到 '(' 将其入栈
            operatorStack.push(static_cast<int>(token));
        } else if (token == ')') {
            // 遇到 ')' 不断弹出栈中的运算符直到 '('
            bool foundMatchingParen = false;
            while (true) {
                int top;
                if (!operatorStack.pop(top)) {
                    result = "Expression is wrong!";
                    return false;  // 括号不匹配
                }
                if (top == '(') {
                    foundMatchingParen = true;
                    break;  // 找到匹配的 '('
                }
                postfix << static_cast<char>(top) ;//<< ' ';
            }
            if (!foundMatchingParen) {
                result = "Expression is wrong!";
                return false;
            }
        } else if (precedence.count(token)) {  
            // 如果是运算符
            while (true) {
                int top;
                if (!operatorStack.getTop(top) || top == '(' || precedence[token] > precedence[static_cast<char>(top)]) {
                    break;  // 当前运算符优先级更高或栈为空
                }
                operatorStack.pop(top);
                postfix << static_cast<char>(top);// << ' ';
            }
            operatorStack.push(static_cast<int>(token));
        } else {
            result = "Expression is wrong!";
            return false;  // 非法字符
        }
    }
    // 检查栈中剩余的运算符，遇到 '(' 说明括号不匹配
    while (true) {
        int top;
        if (!operatorStack.pop(top)) break;  // 栈空结束
        if (top == '(') {  // 栈中存在未匹配的 '('
            result = "Expression is wrong!";
            return false;
        }
        postfix << static_cast<char>(top);// << ' ';
    }
    result = postfix.str();
    return true;
}
bool expressionVal(const string& infix, int& result) {
    string postfix;
    if (!postfixExpression(infix, postfix)) {
        result = 0;
        return false; // 中缀表达式转换失败
    }
    MyStack operandStack;
    int a, b;
    for (size_t i = 0; i < postfix.size(); ++i) {
        char token = postfix[i];
        if (token == ' ') continue; // 跳过空格

        if (isdigit(token)) {
            operandStack.push(token - '0'); // 将数字压入栈中
        } else {
            if (!operandStack.pop(b) || !operandStack.pop(a)) {
                result = 0;
                return false; // 表达式错误
            }
            switch (token) {
                case '+':
                    operandStack.push(a + b);
                    break;
                case '-':
                    operandStack.push(a - b);
                    break;
                case '*':
                    operandStack.push(a * b);
                    break;
                case '/':
                    if (b == 0) {
                        result = 0;
                        return false; // 除数为0，表达式错误
                    }
                    operandStack.push(a / b);
                    break;
                default:
                    result = 0;
                    return false; // 无效运算符，表达式错误
            }
        }
    }
    return operandStack.pop(result); // 结果存入result
    if (!operandStack.pop(result) || !operandStack.getTop(result)) {
        result = 0; // 栈中元素不匹配
        return false;
    }
    return true;
}
void yanghui(const int& numRows) {
    if (numRows <= 0) return;
    MyQueue rowQueue(numRows + 1);  // 容量大于等于行数以存储每行元素
    rowQueue.enQueue(1);  // 初始化第一行
    for (int i = 1; i <= numRows + 1; ++i) {
        int prev = 0;   // 用于保存上一行的元素
        int curr;
        for (int j = 0; j < i; ++j) {
            rowQueue.deQueue(curr);
            if(i > 1)
            cout << curr;
            if(j < i - 1)cout << ',';
            int next = prev + curr;
            prev = curr;
            rowQueue.enQueue(next);  // 将当前元素的下一行值入队
        }
        if(i > 1)
        cout << endl;
        rowQueue.enQueue(1);  // 每行末尾补充1
    }
}